import java.util.*;

    /**
     * @Author 12629
     * @Description：
     */
    public class BinaryTree {

        static class TreeNode {
            public char val;
            public TreeNode left;
            public TreeNode right;

            public TreeNode(char val) {
                this.val = val;
            }
        }

        public TreeNode root;

        /**
         * 创建一棵二叉树 创建成功后 返回根节点
         * @return
         */
        public TreeNode createTree() {
            TreeNode A = new TreeNode('A');
            TreeNode B = new TreeNode('B');
            TreeNode C = new TreeNode('C');
            TreeNode D = new TreeNode('D');
            TreeNode E = new TreeNode('E');
            TreeNode F = new TreeNode('F');
            TreeNode G = new TreeNode('G');
            TreeNode H = new TreeNode('H');

            A.left = B;
            A.right = C;
            B.left = D;
            B.right = E;
            C.left = F;
            C.right = G;
            E.right = H;

            return A;
        }

        // 前序遍历
        void preOrder(TreeNode root){
            if(root == null) {
                return;
            }
            System.out.print(root.val+" ");
            preOrder(root.left);
            preOrder(root.right);
        }

        void preOrderNor(TreeNode root){
            if(root == null) {
                return;
            }
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root;
            while (cur != null || !stack.isEmpty()) {
                while (cur != null) {
                    stack.push(cur);
                    System.out.print(cur.val + " ");
                    cur = cur.left;
                }
                TreeNode top = stack.pop();
                cur = top.right;
            }
        }

        /*List<Integer> ret = new ArrayList<>();
         *//**
         * 把 前序遍历的结果 存储到List 当中
         * @param root
         * @return
         */
         List<Character> ret = new ArrayList<>();
    public List<Character> preorderTraversals(TreeNode root) {
        if(root == null) {
            return null;
        }
        ret.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return ret;
    }
    public List<Character> preorderTraversal(TreeNode root) {
        List<Character> list = new ArrayList<>();
        if(root == null) {
            return list;
        }
        list.add(root.val);
        List<Character> leftTree = preorderTraversal(root.left);
        list.addAll(leftTree);
        List<Character> rightTree = preorderTraversal(root.right);
        list.addAll(rightTree);
        return list;
    }
}
